package com.y.utils;

import java.util.Arrays;

/**
 * @author Y2014188432
 * 排序
 */
public class Sort {
    public static void main(String[] args) {
        int[] s = {1,2,3,4,5,6,7,8,9};
        shellSort(s);
        System.out.println(Arrays.toString(s));
    }

    /**
     * 希尔排序
     * @param s 待排序数组
     */
    public static void shellSort(int[] s){
        if (s == null || s.length == 1){
            return;
        }
        // 分组
        for (int gap = s.length/2 ; gap > 0; gap /= 2) {
            // 排序 分组
            for (int i = gap ; i < s.length; i++) {
                int temp = s[i];
                int j = i;
                if (s[j] > s[j - gap]){
                    while (j - gap >=0 && temp > s[j -gap]){
                        s[j] = s[j-gap];
                        j -= gap;
                    }
                }
                s[j] = temp;
            }
        }
    }
    public static void shellSort2(int[] arr){
        //增量gap，并逐步缩小增量
        for (int gap = arr.length/2;gap>0;gap/=2){
            for (int i = gap;i<arr.length;i++){
                int j = i;
                int temp = arr[j];
                if (arr[j]<arr[j-gap]){
                    while (j-gap>=0&&temp<arr[j-gap]){
                        //移动
                        arr[j] = arr[j-gap];
                        j = j-gap;
                    }
                    //当退出while后，就给temp找到插入的位置
                    arr[j] = temp;
                }
            }
        }
    }
}
